import java.util.Arrays;


//class Solution {
//    public int incremovableSubarrayCount(int[] nums) {
//        //优化该算法
//        有想法，但是没有能力实现 放弃了 算法原理听不懂 等以后有时间再弄弄
//
//        int n = nums.length;
//
//        // 1 创建两个数组 f数组表示以当前下标元素为结尾的最长递增子数组 g数组表示以当前下标为结尾的最长递减子数组
//        int[] f = new int[n];
//        int[] g = new int[n];
//        // 先将数组中元素都初始化为最差情况
//        Arrays.fill(f, 1);
//        Arrays.fill(g, 1);
//        // 开始填写数组
//        //(1) 填写严格递增
//        for(int i = 1; i < n; i++) {
//            if(nums[i] > nums[i-1])
//                f[i] += f[i-1];
//        }
//        if (f[n-1] == n) return (1 + n) * n / 2;
//        //（2） 填写严格递减
//        for(int j = n-2; j >= 0; j--) {
//            if(nums[j] < nums[j+1])
//                g[j] += g[j+1];
//        }
//        // 2 使用固定窗口双指针进行枚举子数组
//        int answer = 0;
//        for(int interval = 0; interval < n; interval++) {
//            int left = 0, right = left + interval;
//            while(right < n) {
//                // 判定区间为整个数组、判定区间在中间、判定区间在左边
//                if((left == 0 && right == n-1
//                        || (left != 0 && right != n-1 && g[right+1] == n-right-1 && f[left-1] == left && nums[left-1] < nums[right+1]))
//                        || (right != n-1 && left == 0 && g[right+1] == n-right-1)
//                        || (left != 0 && right == n-1 && f[left-1] == left)) {
//                    answer++;
//                }
//                //单独判断区间在右边的情况，由于整个窗口是向后进行移动的，若是出现左边不为递增，则无需再移动
//                if (left != 0 && f[left-1] != left) {
//                    break;
//                }
//                left += 1;
//                right += 1;
//            }
//        }
//        return answer;
//    }
//
//    public static void main(String[] args) {
//        Solution test = new Solution();
//        int[] arr = new int[100000];
//        for (int i = 1; i <= 100000; i++) {
//            arr[i-1] = i;
//        }
//        System.out.println(test.incremovableSubarrayCount(arr));
//    }
//}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {

    }
    ListNode (int val) {
        this.val = val;
    }
    ListNode (int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

//class Solution {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if (list1 == null) {
//            return list2;
//        }
//        if (list2 == null) {
//            return list1;
//        }
//        if (list1.val <= list2.val) {
//            list1.next = mergeTwoLists(list1.next, list2);
//            return list1;
//        } else {
//            list2.next = mergeTwoLists(list1, list2.next);
//            return list2;
//        }
//    }
//}


//class Solution {
//
//    public ListNode func(ListNode head, ListNode list1, ListNode list2) {
//        if (list1 == null) {
//            head.next = list2;
//            return head;
//        }
//        if (list2 == null) {
//            head.next = list1;
//            return head;
//        }
//        if (list1.val <= list2.val) {
//            head.next = list1;
//            func(head.next, list1.next, list2);
//        } else {
//            head.next = list2;
//            func(head.next,list1, list2.next);
//        }
//        return head;
//    }
//
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        ListNode head = new ListNode(-1, null);
//        return func(head, list1, list2).next;
//    }
//}


//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if (head.next == null) {
//            return head;
//        }
//        ListNode ret = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return ret;
//    }
//}


//class Solution {
//    public ListNode swapPairs(ListNode head) {
//        // 递归出口
//        if (head == null || head.next == null) {
//            return head;
//        }
//        // 先将第三个及之后所有节点转换，并返回转换后的头节点
//        ListNode prev = swapPairs(head.next.next);
//        // 再将当前两个节点转换，并指向前面的节点
//        ListNode cur = head.next;
//        cur.next = head;
//        head.next = prev;
//        return cur;
//    }
//}



//class Solution {
//    public double pow(double x, long n) {
//        if (n == 0) return 1.0;
//
//        double tmp = pow(x, n / 2);
//        if (n % 2 == 0) {
//            return tmp * tmp;
//        } else {
//            return tmp * tmp * x;
//        }
//    }
//
//
//    public double myPow(double x, long n) {
//        if (x == 0) return 0;
//        if (n < 0) {
//            n = -n;
//            return 1 /  pow(x, n);
//        } else {
//            return pow(x, n);
//        }
//    }
//
//    public static void main(String[] args) {
//        Solution test = new Solution();
//        System.out.println(test.myPow(2.0, 10));
//    }
//}

//class Solution {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if (list1 == null) return list2;
//        if (list2 == null) return list1;
//
//        if (list1.val <= list2.val) {
//            list1.next = mergeTwoLists(list1.next, list2);
//            return list1;
//        } else {
//            list2.next = mergeTwoLists(list1, list2.next);
//            return list2;
//        }
//    }
//}

class Test{
    public void func(int[] arr, int n) {
        if (n == arr.length) return;
        func(arr, n+1);
        System.out.printf("%d ", arr[n]);
    }

    public static void main(String[] args) {
        Test test = new Test();
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        test.func(arr, 0);
    }
}


class Solution {
    public ListNode reverseList(ListNode head) {
        // 使用宏观的角度进行思考问题
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        ListNode prev = head.next;
        prev.next = head;
        head.next = null;
        return newHead;
    }
}






